This invention relates generally to interconnected networks of computers and related devices and, more particularly, to techniques facilitating communication between stations connected to widely separated local area networks (LANs). A local area network includes a set of stations or nodes connected to a common communication bus or ring. Typically, all elements of a single LAN are located in a single building or group of buildings. Multiple LANs are often connected together by devices called bridges, to form an extended LAN. A bridge is a device that is connected to more than one LAN, that xe2x80x9clistensxe2x80x9d to message traffic on each of its LANs, and that forwards the traffic onto selected other LANs. The bridge message forwarding operation is limited by a spanning tree algorithm in which all bridges participate. Messages are forwarded only over a loop-free spanning tree, to avoid closed loops and multiple copies of messages. Message forwarding is further controlled by the bridge""s xe2x80x9clearningxe2x80x9d function. Each bridge learns the directional locations of various stations that are the sources of messages it hears, and xe2x80x9cremembersxe2x80x9d these locations for future use in forwarding message traffic.
Multiple LANs and extended LANs may also be interconnected to form wide area networks (WANs). The mechanism through which extended LANs are interconnected is typically through devices such as routers. At a broad conceptual level, routers perform a similar task to bridges in that each router is connected to multiple LANs or extended LANs. However, the router operates at a different protocol layer (known as the network layer), and a router can be used for forwarding traffic only if the source of the traffic cooperates by using a network layer protocol that is understood by the router. A bridge, on the other hand, is a packet switch that is xe2x80x9ctransparent.xe2x80x9d A station that does not have a network layer protocol, or has a network layer protocol that is not implemented by the router, can use the bridge as a packet switch. Unfortunately, however, bridges have significant drawbacks that preclude their use in many contexts.
The most significant drawback of a bridge, as compared with a router, is that bridges use only a subset of the actual topology of the interconnected networks. In particular, redundant paths cannot be used, because to do so would result in closed loops and unwanted multiplication of message traffic. As already mentioned, to ensure a loop-free topology, bridges participate in a spanning tree algorithm, which establishes a loop-free tree structure. If two extended LANs were to be interconnected by a bridge, the separate spanning trees of the two networks would have to be combined, forming one larger extended LAN. This might not be desirable from a network administration standpoint. Another important disadvantage of bridges is that they cannot forward traffic through a router, because the packets handled by the bridge do not necessarily have the appropriate network layer information needed to utilize the router. Also, since routers do not participate in the spanning tree algorithm, there is a possibility of forming loops in the topology if bridges were to forward traffic through routers.
In summary, neither routers nor bridges provide an ideal solution to the problems of forwarding message traffic over wide-area networks. Some communication protocols cannot work through routers, since routers support only certain network layer protocols. But bridges are limited, by the spanning tree algorithm, to a subset of the overall network topology, and cannot be used to forward traffic through routers that separate LANs. U.S. Pat. No. 5,150,360 issued Sep. 22, 1992, entitled xe2x80x9cUtilization of Redundant Links in Bridged Networksxe2x80x9d (which is owned by the assignee of the present application), provides for the establishment of point-to-links outside the spanning tree, but still does not permit forwarding of traffic through traditional routers.
What is needed is a new approach that permits traffic to be forwarded transparently across WANs, using more optimal routes and permitting the traffic to traverse traditional routers. The present invention satisfies this need.
Another way of viewing the problem that this invention solves is that, ideally, there should be some way to address messages directly to particular extended LANs. However, the addressing conventions that have evolved for interconnected networks do not include any convenient means for addressing extended LANs. What is needed then, is some way of forwarding a message more directly to the extended LAN in which the message destination is located. The present invention also satisfies this need.
The present invention resides in a method and apparatus for logically interconnecting local area networks and extended local area networks, even if they are separated by wide area networks having traditional routers.
Briefly, the method of the invention includes the steps of providing a number of devices with the capability to form xe2x80x9ctunnelsxe2x80x9d between LANs that may be widely separated, these special devices being referred to as tunnelers; then electing a unique designated tunneler for each LAN (LAN) for which tunneling is to be provided. Each LAN has no more than one designated tunneler, but a single tunneler may be designated by more than one LAN. The next steps are configuring the tunnelers, by supplying each with information identifying other tunnelers with which a tunnel may be established, establishing at least one tunnel between two designated tunnelers by exchanging messages between the two tunnelers, if the configuration rules state that such a tunnel should exist, and then selectively forwarding message traffic through the established tunnel, from one LAN to another.
In a preferred embodiment of the invention, the step of electing a unique designated tunneler for each LAN includes executing a spanning tree algorithm among all of the devices connected to the LAN, thereby electing a root device. Since not all devices will necessarily have tunnel capability, some adjustment may be needed to device priorities used in the spanning tree algorithm, to ensure that the root device does have tunneling capability. In this way, the election of a designated tunneler is conveniently effected by means of the existing spanning tree algorithm.
The step of configuring the tunnelers includes supplying to each tunneler the identities of other tunnelers and the identities of ports through which the other tunnelers are connected to LANs with which the ports are associated. The step of establishing a tunnel includes transmitting a greeting from a designated tunneler to each other tunneler that is a potential tunnel endpoint, receiving a message from one of the potential tunnel endpoints confirming that a tunnel may be established, and recording the successful establishment of a tunnel. Establishing a tunnel may also include the steps of transmitting a greeting to at least one backup tunneler, after failing to receive a confirming message from the other designated tunneler; then receiving a message from the backup tunneler confirming that a tunnel may be established; and finally recording the successful establishment of the tunnel. The step of selectively forwarding message traffic through the established tunnel includes the steps of receiving a message at a tunneler, and determining whether the message destination is known to the tunneler. If the destination is known, the method further includes the steps of determining whether a tunnel is required to reach this particular destination, and, if so, forwarding the message through the tunnel, if the tunnel has been established and the message is of a type authorized for forwarding through the tunnel.
If the destination is not known, a subsequent step in the method is determining whether the message was received from a tunnel. If so, the message is forwarded through a port defined as the tunnel endpoint. If the message was not received from a tunnel and the message destination is not known, the method further includes forwarding the message over all non-tunnel ports in the spanning tree, except the one through which the message was received, and forwarding the message through all established tunnels, if any, for which this tunneler is a sending endpoint, if the message is of a type authorized for transmission through the tunnel.
Forwarding a message through a tunnel includes the step of appending to the message a destination address comprising the address of a receiving endpoint tunneler of the tunnel, and a port identifier that also defines, in part, the receiving endpoint of the tunnel. Then the message is transmitted through an appropriate port to reach the receiving endpoint of the tunnel. If the message was received from a tunnel, the method further comprises the step of stripping the tunnel receiving endpoint address from the received message, before forwarding it through the tunnel receiving endpoint port.
In an alternate embodiment of the invention, the configuring step is optimized for specific network topologies. In this case the step of configuring includes supplying the tunnelers with a subset of information concerning other tunnelers, the subset of information being-optimized for a particular network topology. The step of establishing a tunnel then includes one or more of the following steps:
(1) for a designated tunneler, sending a greeting to another designated tunneler with which it has been configured, and receiving a response confirming that a tunnel has been established;
(2) for a designated tunneler, sending a greeting to a nondesignated tunneler with which it has been configured, receiving a refusal response identifying a designated tunneler, redirecting the greeting to the designated tunneler identified in the refusal response, and receiving a response confirming that a tunnel has been established; and
(3) for a nondesignated tunnerler, periodically transmitting multicast messages identifying the tunnelers with which it has been configured, and, for a designated tunneler, responding to a multicast message from a nondesignated tunneler, by sending a greeting to one of the tunnelers contained in the multicast message, and receiving a response message confirming that a tunnel has been established.
The optimized configuration approach reduces the burden of having to manually configure every tunneler with knowledge of every other tunneler. The cost of this simplification is some added complexity in the establishment of tunnels, but the approach is worthwhile for some network topologies.
It will be understood that the invention also encompasses equivalent apparatus claims similar in scope to the various forms of the method discussed above.
It will be appreciated from the foregoing that the present invention represents a significant advance in the field of communication networks. In particular, the invention provides a novel way of logically interconnecting two LANs, even through they may be separated by wide area networks containing routers. The tunneling protocol of the invention effects this logical interconnection in a manner that permits user controlled filtering of the tunnel traffic, and precludes the formation of any closed loops. Traffic filtering may fulfill any desired network administration objectives, such as limiting traffic flow through a tunnel to selected protocols, or limiting flow through a tunnel to traffic having selected destination or source addresses. Other aspects and advantages of the invention will become apparent from the following more detailed description, taken in conjunction with the accompanying drawings.